package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/8/17.<br><br>
 *
 * 中等：搜索旋转排序数组 II
 */
public class Topic81 {
    public static void main(String[] args) {
        Topic81 instance = new Topic81();

        int[] array = new int[] {2,5,6,0,0,1,2};
        System.out.println(instance.search(array, 0));

        array = new int[] {2,5,6,0,0,1,2};
        System.out.println(instance.search(array, 3));

        array = new int[] {1};
        System.out.println(instance.search(array, 0));
    }

    public boolean search(int[] nums, int target) {
        int index = help(nums, 0, nums.length - 1);

        boolean result;
        if(index == -1) {
            result = help2(nums, 0, nums.length - 1, target);
        }
        else {
            if(target >= nums[0]) {
                result = help2(nums, 0, index - 1, target);
            }
            else {
                result = help2(nums, index, nums.length - 1, target);
            }
        }

        return result;
    }

    private int help(int[] nums, int left, int right) {
        if(left > right) {
            return -1;
        }

        int mild = (left + right) / 2;
        if(mild > 0 && nums[mild - 1] > nums[mild]) {
            return mild;
        }

        int resultL = help(nums, left, mild - 1);
        int resultR = help(nums, mild + 1, right);

        return resultL != -1 ? resultL : resultR;
    }

    private boolean help2(int[] nums, int left, int right, int target) {
        if(left > right) {
            return false;
        }

        int mild = (left + right) / 2;
        if(nums[mild] == target) {
            return true;
        }

        boolean resultL = help2(nums, left, mild - 1, target);
        boolean resultR = help2(nums, mild + 1, right, target);

        return resultL | resultR;
    }

    public boolean search2(int[] nums, int target) {
        for(int value : nums) {
            if(value == target) {
                return true;
            }
        }

        return false;
    }
}
